package com.github.yangyishe;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

/**
 * 对909问题的优化
 */
public class Problem909b {
    public static void main(String[] args) {
        int[][] board=new int[][]{
                {-1,-1,-1,-1,48,5,-1},
                {12,29,13,9,-1,2,32},
                {-1,-1,21,7,-1,12,49},
                {42,37,21,40,-1,22,12},
                {42,-1,2,-1,-1,-1,6},
                {39,-1,35,-1,-1,39,-1},
                {-1,36,-1,-1,-1,-1,5}
        };
        Problem909b problem909 = new Problem909b();
//        Map<Integer, Integer> bridgeMap = problem909.convertBridgeMap(board);
//        System.out.println(bridgeMap);


        int i = problem909.snakesAndLadders(board);
        System.out.println(i);

    }

    /**
     * 思路:
     * 模型结构,类似图.
     * 实际解决,肯定要通过递归+回溯的方法.
     * 在思路1中, 虽然给出了解决方案, 但效率太低. 而要提升效率, 最好的方式是对于非最佳方案提前返回.
     *
     * 本类中采用的思路是, 构建一个map(实际用arr即可)记录到所有节点的最小步骤.
     * 这个最小步骤,不再采用返回值逆加, 而用参数正加
     *
     *
     * @param board
     * @return
     */
    public int snakesAndLadders(int[][] board) {
        Map<Integer, Integer> bridgeMap = convertBridgeMap(board);
        size=board.length* board.length;
        minStepArr=new int[size+1];

        step(1,bridgeMap,1);

        return minStepArr[size]==0?-1:minStepArr[size];
    }

    private int size;
    private int[] minStepArr;

    private void step(int start,Map<Integer,Integer> bridgeMap,int currentStep){
        if(start>size){
            return;
        }
        int maxNormalStep=0;
        boolean canTouch;
        for(int i=1;i<=6;i++){
            Integer jmpPosition= bridgeMap.get(start+i);
            if(jmpPosition==null){
                canTouch=touchPosition(start+i,currentStep);
                if(canTouch){
                    maxNormalStep=start+i;
                }
            }else{
                canTouch=touchPosition(jmpPosition,currentStep);
                if(canTouch){
                    step(jmpPosition,bridgeMap,currentStep+1);
                }
            }
        }
        if(maxNormalStep!=0){
            step(maxNormalStep,bridgeMap,currentStep+1);
        }
    }

    private boolean touchPosition(int position,int currentStep){
        if(position>size){
            return false;
        }
        if(minStepArr[position]==0||minStepArr[position]>currentStep){
            minStepArr[position]=currentStep;
            return true;
        }else{
            return false;
        }
    }

    /**
     * 转换为稀疏数组
     * @param board
     * @return
     */
    private Map<Integer,Integer> convertBridgeMap(int[][] board){
        int n=board.length;
        int csum=0;
        int rsum;
        Map<Integer,Integer> bridgeMap=new HashMap<>();
        // 遍历方式:从左下角开始遍历
        for(int r=n-1;r>=0;r--){
            rsum=0;
            if((n-1-r)%2==0){
                for(int c=0;c<n;c++){
                    rsum++;
                    if(board[r][c]!=-1){
                        bridgeMap.put(csum+rsum,board[r][c]);
                    }
                }
            }else{
                for(int c=n-1;c>=0;c--){
                    rsum++;
                    if(board[r][c]!=-1){
                        bridgeMap.put(csum+rsum,board[r][c]);
                    }
                }
            }

            csum+=n;
        }

        return bridgeMap;
    }
}
